/**
 * TP n°:
 *
 * Titre du TP : Defi 1
 *
 * Date : 25 oct 2010
 *
 * Nom  : NGUYEN
 * Prenom : Quang Hoang
 *
 * Remarques :
 */
#include "graph.h"
#include <stdlib.h>

#define DENSITE(n,m) (((float) 2*(m)) / (float)((n)*(n-1)))

int sort(const void *x, const void *y) {
  return (*(int*)x - *(int*)y);
}

int main(int *argc, char **argv)
{
  FILE *f = fopen(argv[1], "r");
  GRAPH *G;
  long i;
  long next;

  G = graph_from_file(f, atol(argv[2]));
  fclose(f);
  printf(" noeuds : %ld\n liens : %ld\n densite : %4.2f\n",
	  G->n, G->m, DENSITE(G->n, G->m));
  //traverser la graphe
  printf("\nBegin Sorting G\n");
  for(i=0; i<G->n; i++){
	  if(i%100 == 0){
		  printf("Sorting... %4.2f %\r", 100*(float)i/((float)G->n));
	  }
	  //trier la table de voisins
	  qsort(G->links[i], G->degrees[i], sizeof(long), sort);
	  /*printf("node %ld 's neighbors:",i);
	  for(next = 0; next < G->degrees[i]; next++){
		  printf(" %ld",G->links[i][next]);
	  }
	  printf("\n");*/
  }
  printf("\nSorting done!\n");

  //algorithm 1

  long u = 0;
  long v = 5;

  long iu = 0;
  long iv = 0;
  printf("\nChercher des triangles dont 2 sommets sont %ld et %ld\n",u,v);
  while ((iu < G->degrees[u]) && (iv < G->degrees[v])){
	  if (G->links[u][iu]<G->links[v][iv]){
	    iu++;
	  }
	  else if (G->links[u][iu]>G->links[v][iv]){
	    iv ++ ;
	  }
	  else{
		printf(" Triangle entre %ld , %ld et %ld\n",u,v, G->links[u][iu]);
	    iu++ ; iv++ ;
	  }
  }
  printf("Done chercher des triangles contenant %ld %ld !\n",u,v);

  //Algorithm 2: Algo final
  //Result: Tableau tr qui contient le nombre de triangle de chaque sommet
  printf("\nCreate Tableau triangles[] qui contient le nombre de triangle de chaque sommet.\n");
//  long tr[G->n];// : tableau de taille n initialisé à 0;
  long* triangles = malloc(G->n * sizeof(long));

  for(i = 0; i<G->n; i++){
	  triangles[i] = 0;
  }
//  printf("Init triangles[] done!\n");
  for(v = 0; v < G->n; v++){
	  if(v%100 == 0){
		  printf("Creating triangles[]... %4.2f %\r", 100*(float)v/((float)G->n));
	  }
	  for(i = 0 ;i < G->degrees[v] ;i++){
		  u = G->links[v][i]; //i-ème voisin de v;
		  if(u > v){
			  iu = 0;
			  iv = 0;
			  while((iu < G->degrees[u]) && (iv < G->degrees[v]) && (G->links[u][iu]<v) && (G->links[v][iv]<v)){
				  // Ce while est une variante de l’algorithme 1;
				  if(G->links[u][iu]<G->links[v][iv]){
					  iu++;
				  }
				  else if( G->links[u][iu]>G->links[v][iv]){
					  iv++;
				  }
				  else{
					  triangles[u]++;
					  triangles[v]++;
					  triangles[G->links[u][iu]]++;
					  iu++;
					  iv++;
				  }
			  }
		  }
	  }
  }
  printf("\nCreate triangles[] done!\n");

  unsigned long numTriangle = 0;
  unsigned long numTriplet = 0;

  for(i = 0; i<G->n; i++){
	  numTriangle += triangles[i];
//  	  printf("triangles[%ld]=%ld\n",i,triangles[i]);
	  unsigned long deg = G->degrees[i];
	  deg = deg * (deg - 1) / 2;
	  /*if(deg <= 0){
		 printf("Error: deg[%ld] = %ld\n",i,deg);
	  }*/
	  if(deg > 0){
		  numTriplet += deg;
	  }
  }
  numTriangle = numTriangle / 3;
  printf("Nombre de triangle: %ld\n",numTriangle);
  printf("Nombre de triplet : %ld\n",numTriplet);
  printf("Coefficient clutering global du G: gcc(G) = %f\n",3 * (float)numTriangle / (float)numTriplet);

//  graph_to_file(stdout, G);
  return 0;
}
